/*
 * @lc app=leetcode.cn id=23 lang=c
 *
 * [23] 合并 K 个升序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//  struct ListNode {
//      int val;
//      struct ListNode *next;
//  };

struct ListNode *merge2Lists(struct ListNode *list1, struct ListNode *list2)
{
    struct ListNode *ret = malloc(sizeof(struct ListNode));
    struct ListNode *cur = ret;
    cur->next = NULL;

    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            cur->next = list1;
            list1 = list1->next;
        }
        else
        {
            cur->next = list2;
            list2 = list2->next;
        }
        cur = cur->next;
    }
    if (list1)
    {
        cur->next = list1;
    }
    if (list2)
    {
        cur->next = list2;
    }
    return ret->next;
};

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize)
{
    int interval = 1;
    int i;
    while (interval < listsSize)
    {
        for (i = 0; i < listsSize - interval; i += interval * 2)
        {
            lists[i] = merge2Lists(lists[i], lists[i + interval]);
        }
        interval *= 2;
    }
    return listsSize > 0 ? lists[0] : NULL;
}
// @lc code=end
